|
In automata theory, a Muller automaton is a type of an ω-automaton. The acceptance condition separates a Muller automaton from other ω-automata. The Muller automata is defined using Muller acceptance condition, i.e. the set of all states visited infinitely often must be an element of the acceptance set. Both deterministic and non-deterministic Muller automata recognize the ω-regular languages. They are named after David E. Muller an American mathematician and computer scientist, who invented them in 1963. ==Formal definition== Formally, a deterministic Muller-automaton is a tuple ''A'' = (''Q'',Σ,δ,''q''0,F) that consists of the following information: * ''Q'' is a finite set. The elements of ''Q'' are called the ''states'' of ''Q''. * Σ is a finite set called the ''alphabet'' of ''A''. * δ: ''Q'' × Σ → ''Q'' is a function, called the ''transition function'' of ''A''. * ''q''0 is an element of ''Q'', called the initial state. * F is a set of sets of states. Formally, F ⊆ P(''Q'') where P(''Q'') is powerset of ''Q''. F defines the ''acceptance condition''. ''A'' accepts exactly those runs in which the set of infinitely often occurring states is an element of ''F'' In a non-deterministic Muller automaton, the transition function δ is replaced with a transition relation Δ that returns a set of states and initial state is ''q''0 is replaced by a set of initial states ''Q''0. Generally, Muller automaton refers to non-deterministic Muller automaton. For more comprehensive formalism look at ω-automaton. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Muller automaton」の詳細全文を読む スポンサード リンク
|